<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>哈希表扩容</title>
  </head>
  <body>
    <script>
      // 创建HashTable构造函数
      function HashTable() {
        // 定义属性
        this.storage = [] // storage作为我们的数组, 数组中存放相关的元素.
        this.count = 0 // count表示当前已经存在了多少数据.
        this.limit = 8 //  limit用于标记数组中一共可以存放多少个元素.

        // 定义相关方法
        // 哈希函数
        HashTable.prototype.hashFunc = function(str, max) {
          // 1.初始化hashCode的值
          let hashCode = 0

          // 2.霍纳算法, 来计算hashCode的数值
          for (let i = 0; i < str.length; i++) {
            hashCode = 37 * hashCode + str.charCodeAt(i)
          }

          // 3.取模运算
          hashCode = hashCode % max
          return hashCode
        }
        
        
        //resize方法 哈希表扩容
        HashTable.prototype.resize = function(newLimit) {
          // 1.保存旧的数组内容
          let oldStorage = this.storage
        
          // 2.重置属性
          this.limit = newLimit
          this.count = 0
          this.storage = []
        
          // 3.遍历旧数组中的所有数据项, 并且重新插入到哈希表中
          oldStorage.forEach(function(bucket) {
            // 1.bucket为null, 说明这里面没有数据
            if (bucket == null) {
              return
            }
            // 2.bucket中有数据, 那么将里面的数据重新哈希化插入
            for (let i = 0; i < bucket.length; i++) {
              let tuple = bucket[i]
              this.put(tuple[0], tuple[1])
            }
          }.bind(this))
          /* .bind()创建了一个函数,当这个函数在被调用的时候,
          它的this关键词会被设置成被传入的值（这里指调用bind()时传入的参数 */
        }
        
        //isPrime方法 判断是不是质数
        HashTable.prototype.isPrime = function(num) {
          let temp = parseInt(Math.sqrt(num))
          for (let i = 2; i <= temp; i++) {
            if (num % i == 0) {
              return false
            }
          }
          return true
        }
        
        //getPrime方法 获取质数
        HashTable.prototype.getPrime = function(num) {
          while (!isPrime(num)) {
            num++
          }
          return num
        }
        
        //1.put方法 插入&&修改
        HashTable.prototype.put = function(key, value) {
          // 代码解析:

          // 步骤1: 根据传入的key获取对应的hashCode, 也就是数组的index,
          let index = this.hashFunc(key, this.limit)
          // 步骤2: 从哈希表的index位置中取出桶(另外一个数组)
          let bucket = this.storage[index]
          // 步骤3: 查看上一步的bucket是否为null,
          // 为null, 表示之前在该位置没有放置过任何的内容, 那么就新建一个数组[]
          if (bucket === undefined) {
            bucket = []
            this.storage[index] = bucket
          }
          // 步骤4: 查看是否之前已经放置过key对应的value,
          // 如果放置过, 那么就是依次替换操作, 而不是插入新的数据.我们使用一个变量override来记录是否是修改操作
          let override = false
          for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i]
            if (tuple[0] === key) {
              tuple[1] = value
              override = true
            }
          }
          // 步骤5: 如果不是修改操作, 那么插入新的数据.
          // 在bucket中push新的[key, value]即可.
          // 注意: 这里需要将count+1, 因为数据增加了一项.
          if (!override) {
            bucket.push([key, value])
            this.count++

            // 数组扩容
            if (this.count > this.limit * 0.75) {
              let primeNum = this.getPrime(this.limit * 2)
              this.resize(primeNum)
            }

          }
        }
        
        //2.get方法获取
        HashTable.prototype.get = function(key) {
          // 代码解析:

          // 步骤1: 根据key获取hashCode(也就是index)
          let index = this.hashFunc(key, this.limit)
          // 步骤2: 根据index取出bucket.
          let bucket = this.storage[index]
          // 步骤3: 因为如果bucket都是null, 那么说明这个位置之前并没有插入过数据.
          if (bucket === null) {
            return null
          }
          // 步骤4: 有了bucket, 就遍历, 并且如果找到, 就将对应的value返回即可.
          for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i]
            if (tuple[0] === key) {
              return tuple[1]
            }
          }
          // 步骤5: 没有找到, 返回null
          return null
        }
        
        // 3.remove方法删除
        HashTable.prototype.remove = function(key) {
          // 代码解析:

          // 步骤1: 根据key获取hashCode(也就是index)
          let index = this.hashFunc(key, this.limit)
          // 步骤2: 根据index取出bucket.
          let bucket = this.storage[index]
          // 步骤3: 因为如果bucket都是null, 那么说明这个位置之前并没有插入过数据.
          if (bucket === null) {
            return null
          }
          // 步骤4: 有了bucket, 线性查找删除
          for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i]
            if (tuple[0] === key) {
              bucket.splice(i, 1)
              this.count--
              return tuple[1]

              // 缩小数组的容量
              if (this.limit > 7 && this.count < this.limit * 0.25) {
                let primeNum = this.getPrime(Math.floor(this.limit / 2))
                this.resize(primeNum)
              }

            }
          }
          // 步骤5: 没有找到, 返回null
          return null
        }
        
        //4. isEmpty方法
        HashTable.prototype.isEmpty = function() {
          return this.count == 0
        }
        
        // 5.size方法
        HashTable.prototype.size = function() {
          return this.count
        }

      }

      // 测试哈希表
      // 1.创建哈希表
      let ht = new HashTable()

      // 2.插入数据
      ht.put("abc", "123")
      ht.put("cba", "321")
      ht.put("nba", "521")
      ht.put("mba", "520")
      ht.put("mba", "523")
      console.log(ht)
      // 3.获取数据
      alert(ht.get("abc"))
      ht.put("abc", "111")
      alert(ht.get("abc"))

      // 4.删除数据
      alert(ht.remove("abc"))

      alert(ht.get("abc"))

      ht.put("abc", "1314")

      alert(ht.isEmpty())

      alert(ht.size())
    </script>
  </body>
</html>
